package _binary_search;

import java.util.Arrays;
import java.util.Comparator;

/**
 * 436. 寻找右区间
 */
public class No436 {
    public int[] findRightInterval(int[][] intervals) {
        int n = intervals.length;
        int[][] tempArr = new int[n][2];
        for (int i = 0; i < n; i++) {
            tempArr[i][0] = intervals[i][0];
            tempArr[i][1] = i;
        }
        Arrays.sort(tempArr, Comparator.comparingInt(o -> o[0]));
        int[] answer = new int[n];
        for (int i = 0; i < intervals.length; i++) {
            int tempArrIndex = lowerBound(tempArr, intervals[i][1]);
            answer[i] = tempArrIndex == n ? -1 : tempArr[tempArrIndex][1];
        }
        return answer;
    }

    private int lowerBound(int[][] ints, int target) {
        int n = ints.length;
        int left = 0, right = n - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (ints[mid][0] < target) left = mid + 1;
            else right = mid - 1;
        }
        return left;
    }
}
